from lxml import etree

def toTagString(element):
    print '<'+element.tag+'>',
    for elem in element.iterchildren():
        toTagString(elem)
    print '</'+element.tag+'>',

def toTagList(element, lst=None):
    if lst == None:
        lst = []
    lst.append('<'+element.tag+'>')
    for elem in element.iterchildren():
        toTagList(elem, lst)
    lst.append('</'+element.tag+'>')
    return lst

def elementIterator(element):
    yield element
    for elem in element.iterchildren():
        for r in elementIterator(elem):
            yield r
    yield element

def lcs(seq1, seq2):
    curr = [0] * (1 + len(seq2))
    for x in seq1:
        prev = list(curr)
        for i, y in enumerate(seq2):
            if x == y:
                curr[i + 1] = prev[i] + 1
            else:
                curr[i + 1] = max(prev[i + 1], curr[i])
    return curr[-1]

def editDistance(seq1, seq2):
    return max(len(seq1), len(seq2)) - lcs(seq1, seq2)

